package com.algorithm.动态规划;

/**
 * 有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 𝑤i、价值是 𝑣i
 * 在保证总重量不超过 W 的前提下，选择某些物品装入背包，背包的最大总价值是多少?
 * 注意:每个物品只有 1 件，也就是每个物品只能选择 0 件或者 1 件
 */
public class 背包问题 {
    public static void main(String[] args) {
        int[] value = {6, 3, 5, 4, 6};
        int[] weight = {2, 2, 6, 5, 4};
        int capacity = 10;
        System.out.println(maxValue(value, weight, capacity));
    }

    /**
     * 动态规划
     *
     * @param value
     * @param weight
     * @param capacity
     * @return
     */
    private static int maxValue(int[] value, int[] weight, int capacity) {
        if (value == null || value.length == 0) return 0;
        if (weight == null || weight.length == 0) return 0;
        if (value.length != weight.length || capacity < 0) return 0;
        int[][] dp = new int[value.length + 1][capacity + 1];
        for (int i = 1; i <= value.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weight[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
                }
            }
        }
        return dp[value.length][capacity];
    }
}
